package com.ai.zuochengyun.phase01.class01;

/**
 * 给定一个数组arr，两个整数lower和upper，返回arr中有多少个子数组的累加和在lower和upper上
 * https://blog.csdn.net/cy973071263/article/details/125123830
 */
public class Code09_CountRangeSum {

    public static void main(String[] args) {
        System.out.println("开始统计");
        for (int i = 0; i < 10; i++) {
            // 生成[2,11]范围的值
            int size = (int)(Math.random() * 10)+2;
            int[] arr = new int[size];
            int total = 0;
            for (int j = 0; j < size; j++) {
                int num = (int)(Math.random() * 10)*30+2 - ((int)(Math.random() * 10)*10+2);
                arr[j] = num;
                total+= num;
            }
            int a = 0;
            do {
                a = (int)(Math.random() * 10)*30;
            } while (a < 0 || a > total);
            int b = 0;
            do {
                b = (int)(Math.random() * 10)*20;
            } while (b < 0 || b > total);

            int lower = Math.min(a, b);
            int upper = Math.max(a, b);
            if (lower == upper) {
                upper++;
            }
            int[] arr2 = new int[size];
            System.arraycopy(arr2, 0, arr, 0, size);
            int num2 = countRangeSum2(arr,  lower, upper);
            int num1 = countRangeSum(arr2, lower, upper);
            if (num1 != num2) {
                System.out.println("统计结果不匹配，sum[0,n-1]="+total+",lower="+lower+",upper="+upper);
                System.out.println("num1="+num1+",num2="+num2);
                for (int j = 0; j < arr.length; j++) {
                    System.out.print(arr[j] + " ");
                }
                return;
            }
        }
        System.out.println("结束统计");
    }

    private static int countRangeSum(int[] arr, int lower, int upper) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 转换成前缀和
        int[] sum = new int[arr.length];
        sum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            // 前面的和 加上 当前数
            sum[i] = sum[i-1] + arr[i];
        }
//        System.out.println(Arrays.toString(sum));

        return process(sum, 0, arr.length -1, lower, upper);
    }

    private static int test(int[] arr, int lower, int upper) {
        int ans = 0;
        for (int i = 0; i < arr.length; i++) {
            int sum = 0;
            for (int j = i; j >= 0; j--) {
                sum+= arr[j];
                if (sum >= lower && sum <= upper) {
                    ans++;
                }
            }
        }
        return ans;
    }

    private static int countRangeSum2(int[] arr, int lower, int upper) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        // 转换成前缀和
        int[] sum = new int[arr.length];
        sum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            // 前面的和 加上 当前数
            sum[i] = sum[i-1] + arr[i];
        }
//        System.out.println(Arrays.toString(sum));

        return process2(sum, 0, arr.length -1, lower, upper);
    }

    private static int process(int[] sum, int left, int right, int lower, int upper) {
        if (left == right) {
            // left代表0~left位置的前缀和
            if (sum[left] >= lower && sum[left] <= upper) {
                return 1;
            }
            return 0;
        }
        int mid = left +((right - left) >>1);
        int leftPart= process(sum, left, mid, lower, upper);
        int rightPart= process(sum, mid+1, right, lower, upper);
        return leftPart+rightPart+merge(sum, left, mid, right, lower, upper);
    }

    private static int process2(int[] sum, int left, int right, int lower, int upper) {
        if (left == right) {
            // left代表0~left位置的前缀和
            if (sum[left] >= lower && sum[left] <= upper) {
                return 1;
            }
            return 0;
        }
        int mid = left +((right - left) >>1);
        int leftPart= process2(sum, left, mid, lower, upper);
        int rightPart= process2(sum, mid+1, right, lower, upper);
        return leftPart+rightPart+merge2(sum, left, mid, right, lower, upper);
    }

    private static int merge(int[] sum, int left, int mid, int right, int lower, int upper) {
        if (left > mid || mid > right) {
            System.out.println("下标有误");
            return 0;
        }

        // 统计累加和达标的个数
        int ans = 0;
        for (int i = left; i <= mid; i++) {
            for (int j = mid+1; j <= right; j++) {
                // 左组的数是否在[X-upper, X-lower]区间
                if (sum[i] >= sum[j] - upper && sum[i] <= sum[j] - lower) {
                    ans++;
                }
            }
        }

        // 经典merge排序逻辑
        int size = right - left + 1;
        int[] help = new int[size];
        int index = 0;
        int p1 = left, p2 = mid+1;
        while (p1 <= mid && p2 <= right){
            if (sum[p1] <= sum[p2]) {
                help[index++] = sum[p1++];
            } else {
                help[index++] = sum[p2++];
            }
        }
        while (p1 <= mid){
            help[index++] = sum[p1++];
        }
        while (p2 <= right){
            help[index++] = sum[p2++];
        }
        for (int i = 0; i < help.length; i++) {
            sum[left+i] = help[i];
        }
        return ans;
    }

    /**
     * 教程上的解法
     * @param sum
     * @param left
     * @param mid
     * @param right
     * @param lower
     * @param upper
     * @return
     */
    private static int merge2(int[] sum, int left, int mid, int right, int lower, int upper) {
        if (left > mid || mid > right) {
            System.out.println("下标有误");
            return 0;
        }

        // 统计累加和达标的个数
        int ans = 0;
        // 对于右组中的每个数X，求左组中有多少个数，位于[X-upper, X-lower]范围
        int windowL = left, windowR = left;
        // 遍历右组的数
        for (int i = mid+1; i <= right; i++) {
            int min = sum[i] - upper;
            int max = sum[i] - lower;
            while (windowR <= mid && sum[windowR] <= max) {
                windowR++;
            }
            while (windowL <= mid && sum[windowL] < min) {
                windowL++;
            }
            // 构造了一个左闭右开的区间[windowL, windowR)
            ans += Math.max(0, windowR - windowL);
        }

        // 经典merge排序逻辑
        int size = right - left + 1;
        int[] help = new int[size];
        int p1 = left;
        int p2 = mid + 1;
        int index = 0;
        while (p1 <= mid && p2 <= right) {
            if (sum[p1] <= sum[p2]) {
                help[index++] = sum[p1++];
            } else {
                help[index++] = sum[p2++];
            }
        }
        while (p1 <= mid) {
            help[index++] = sum[p1++];
        }
        while (p2 <= right) {
            help[index++] = sum[p2++];
        }

        // 拷贝回原数组
        for (int i = 0; i < help.length; i++) {
            sum[left + i] = help[i];
        }
        return ans;
    }
}
